This invention relates to Boolean operations for subdivision surfaces.
Computer modeling of surfaces finds use in a number of disciplines, from automotive design to fine art. A number of methods for constructing surfaces, especially smoothly-varying surfaces, have been developed. One example is NURBS surfaces constructed from piecewise polynomial representations. Recently, another method has been developed to construct complex surfaces. Subdivision surface methods allow for constructing any arbitrary surface (e.g., a human face, or a complex, yet smoothly-varying automobile surface) from a number of polygonal "faces".
Subdivision surfaces comprise a significant generalization of the tensor product B-spline surfaces (or the slightly more general NURBS surfaces) which have been widely used in computer aided geometric modeling, as described above. With tensor product surfaces, the control vertices generally require a rectangularly gridded structure, where each interior vertex is connected to four neighboring vertices ("valance=4"). This can place serious restrictions on the designer. (For instance, closed surfaces can require special handling.) One advantage of subdivision surfaces (over NURBS surfaces) is that subdivision surfaces allow control meshes of arbitrary topology. Thus the vertices can have different valences and the faces of the control mesh need not be four sided.
A subdivision surface is generally defined in the following way. One starts with a base polygonal mesh (a set of control vertices together with their corresponding connectivity structure) M.sub.0. A subdivision scheme (consisting of a small number of rules) is applied to yield a refined new mesh M.sub.1, which can be called a derived mesh. (New vertices are introduced, and each old face is thereby replaced by several new smaller ones.) This is repeated recursively to give derived meshes M.sub.n, n=2, 3, . . . , with progressively denser vertices, as in FIGS. 1A through 1D. It can be proved that these polygonal meshes will converge to a limit surface S. This limit surface is called a subdivision surface.
The subdivision rules are adapted from the corresponding rules which hold for B-splines. Hence the tensor product B-spline surfaces form a subclass of subdivision surfaces. Subdivision surfaces were introduced in 1978 by Doo-Sabin (generalizing bi-quadratic splines) and Catmull-Clark (generalizing bi-cubic splines). In the Catmull-Clark scheme, after one subdivision step, (i.e., from M.sub.1 onwards) all faces are quadrilaterals. A different type of subdivision scheme introduced by Loop uses triangular meshes (i.e., meshes with only triangular faces).
Since the subdivision rules for refining meshes are fixed, the final surface S is uniquely determined by the initial mesh M.sub.0. Thus S can be stored compactly as M.sub.0 (or as any M.sub.n since each M.sub.n can be regarded as the base mesh for the same final surface.) The surface S can be modified by simply modifying the control vertices in the base mesh (or in any intermediate mesh M.sub.n, again treated as the new base mesh). One editing system for interactively modifying subdivision surfaces locally by moving selected mesh vertices, is shown in U.S. patent application, Ser. No. 08/839,349, entitled "Editing a Surface", incorporated by reference.
Since S is the limit of M.sub.n, to render the subdivision surface, one can usually and simply render an intermediate mesh M.sub.n at some appropriately large n. Alternatively, one can render S by evaluating the limit surface (points and normals) exactly. One method for evaluating S in this manner is shown in U.S. patent application, Ser. No. 09/116,553, filed Jul. 15, 1998, entitled "Surface Evaluation", incorporated by reference.
One problem with subdivision surfaces is that the base mesh for a complex surface may be difficult or time-consuming to construct. Mesh data for a real surface may be obtained from measurement or scanning of an existing object. This generally results in a rather dense mesh. Moreover, since subdivision does not generally interpolate mesh vertices, the limit surface may not reproduce the original real surface. In free form design, mesh data may be painstakingly entered by a designer and modified later. Modifying a large number of vertices in some intermediate mesh M.sub.n can prove time-consuming.